package leetcode.hot100;

import java.util.*;

public class Solution347 {

    public static void main(String[] args) {

//        [5,2,5,3,5,3,1,1,3]
//        2
        int[] nums = {5,2,5,3,5,3,1,1,3};
        new Solution347().topKFrequent(nums,2);

    }

    public int[] topKFrequent(int[] nums, int k) {
        //键值对，然后按值排序
        HashMap<Integer,Integer> count = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            count.put(nums[i],count.getOrDefault(nums[i],0)+1);
        }
        //用k个节点小顶堆，不超过nlogn，里面存数组[num，频次]，小顶堆会把出现出现次数相同的元素当作一个
        //还是用优先队列
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        //入堆，不满则入，否则：如果要入者比顶大则去顶后入，否则不入
        for (int key: count.keySet()) {
            if(maxHeap.size()==k&&count.get(key)>count.get(maxHeap.peek()[0])) maxHeap.poll();
            if(maxHeap.size()<k) maxHeap.add(new int[]{key,count.get(key)});
        }
        //转int
        int[] res = new int[k];
        int i = 0;
        for (int[] it: maxHeap) {
            res[i] = it[0];
            i++;
        }
        return res;
    }
}
